1. Field of the Invention
The present invention relates in general to random binary identification codes (IDs) subject to bit drift, and in particular to a method of authenticating an object that is, or has attached to it an apparatus, which in turn is, capable of generating such an ID code.
2. Description of Related Art
There are many forms of identification (ID), and IDs are used for many purposes. For example an ID may be provided in printed form (e.g., user-names or bank account numbers), in graphical form (e.g., a picture on a driver license or a barcode on a product), in the form of a magnetic field (e.g., as provided by a magnetic strip on a credit card), as an electronic code conveyed by a signal.
An ID may be used to indicate the type of object bearing the ID. For example, a barcode-encoded UPC on a cereal box in a grocery store enables a grocer to determine the price of the goods when all boxes of the same kind of cereal are printed with the same barcode. An ID may be used to distinguish an object from a population of similar objects. For example a user-name may distinguish one user of a computer network service from all other users of the service, or a bank account number may uniquely distinguish a customer account from all other bank accounts. An ID can be used to confirm that the bearer of an ID is a genuine member of a population. For example, a photograph on a driver""s license is a form of ID used to confirm that the bearer of the driver""s license is the individual named on the driver""s license.
Signals conveying binary strings are often used as ID codes. For example each instance of a particular type of integrated circuit (IC) chip can be made to generate an output signal conveying a unique binary code ID. The ID generated by each IC may be used to distinguish that IC from among all other ICs, to verify that the particular IC is a genuine legitimate copy of an IC and not an illegitimate counterfeit. The ID generated by an IC can also be used to identify any larger electronic system in which it is incorporated. xe2x80x9cRadio Frequency Identificationxe2x80x9d tags (RFIDs) are ICs that produce radio frequency signals conveying binary IDs. When the RFIDs are attached to objects, such as for example merchandise in a retail store, packages for delivery, the unique radio frequency ID codes they generate can serve the same identification purposes as barcodes.
There are many economic or other incentives for people to misuse IDs. For example when an ID identifies goods as having been produced by a particular source, a source of counterfeit goods would want to provide the counterfeit goods with IDs that incorrectly identify them as having been produced by that particular source. Thus counterfeiters not only try to counterfeit goods, they also seek to counterfeit IDs that are associated with those goods. Accordingly efforts have been made to render IDs difficult to copy or counterfeit. For example sophisticated procedures/algorithms and manufacturing processes are sometimes used to make IDs that are difficult for a counterfeiter to copy. A hologram is one example of a difficult to reproduce ID. Sometimes IDs are hidden or encoded in a way that makes it difficult for a would-be counterfeiter to discover them.
One way to foil an ID counterfeiter is to make it hard for the counterfeiter to determine which part of a code is actually being used as an ID. U.S. Pat. No. 5,367,148, issued Nov. 22, 1994 to Storch et al., entitled xe2x80x9cCounterfeit detection using ID numbers with at least one random portion,xe2x80x9d teaches the techniques of adding one or more xe2x80x9crandomxe2x80x9d portions (each consisting of one or more digits) to an otherwise straightforward numerical ID, and of purposely using different presentations in the xe2x80x9cexternalxe2x80x9d appearance (e.g. as printed on the outside package box) of the ID and the xe2x80x9cinnerxe2x80x9d appearance (e.g. inside the box on a customer return registration card), for detecting counterfeits. U.S. Pat. No. 6,212,638, issued Apr. 3, 2001 to Lee et al., entitled xe2x80x9cMethod for generating unpredictable authentication identification symbols,xe2x80x9d teaches use of special mathematical functions to generate sequences of unpredictable ID symbols, and to employ an unpredictable subset of the symbols from such a sequence for an actual ID.
The IDs described by the above-mentioned prior art techniques are xe2x80x9cstaticxe2x80x9d in that, once a particular copy of an ID is generated, it stays the same each time the ID is presented. For example a barcode ID, once printed, never changes its appearance. A product serial number, once imprinted on the casing of a product or printed on a customer registration card, never changes its value. A user-name for logging into an on-line service remains the same once assigned.
U.S. Pat. No. 6,161,213, issued Dec. 12, 2000 to Keith Lofstrom, entitled xe2x80x9cSystem for providing an integrated circuit with a unique identification,xe2x80x9d describes a circuit (currently marketed under the trademark xe2x80x9cICIDxe2x80x9d) that may be incorporated into an IC chip for generating a unique ID for each IC in which it is embedded without requiring each IC to be separately processed. The ICID circuit includes an array of cells, and each cell controls the state of a separate bit of the ID to be generated based on relative doping levels within channels of transistors forming a part of the cell. Since the doping level randomly varies from transistor-to-transistor within an IC as a result of random process variations, the bit sequence of the ID produced by each copy of the ICID circuit is randomly established as the IC is fabricated. When the ID has a sufficiently large number of bits, the ID generated by each copy of the ICID circuit is highly likely to be unique even though a very large number of copies of the ICID circuit are manufactured.
The doping levels of the transistors of one or more of the ID cells of any given copy of an ICID circuit may be so similar that environmental variables such as ambient temperature and supply voltages can influence the ID bit state controlled by those cells. One characteristic of binary IDs produced by the ICID circuit is that a very small percentage of the bits of the ID it generates may not always be of the same state each time the ICID circuit generates the ID; the state of one or more bits of an ID may xe2x80x9cdriftxe2x80x9d in that it changes from instance-to-instance of the generated ID. Thus the ID that the ICID circuit produces is xe2x80x9cdynamicxe2x80x9d in that it does not always have exactly the same value each time it is generated. However Lofstrom teaches that even though a few bits of each individual ID may drift, the ID can still be used to uniquely identify each IC from among a large population of ICIDs producing such IDs if the ID has a sufficiently large number of bits. Lofstrom teaches that two sufficiently long IDs may be considered with a high degree of confidence to have been produced by the same copy of an ICID circuit even though a few of their corresponding bits are not of matching states.
The invention relates to a method for verifying that a particular object, such as for example an integrated circuit (IC), is a member of a population of similar objects.
In accordance with the invention, each population member is configured to generate a binary identification code (ID) that differs from IDs generated by all other members of the population. The ID generated by each member is dynamic in that all instances of the ID generated by a population member may not always have exactly the same value. While bits residing in most of the bit positions of a dynamic ID generated by any population member do not vary in state from instance-to-instance, bits residing in one or more other bit positions of the ID may xe2x80x9cdriftxe2x80x9d in that they may vary in state from instance-to-instance of that ID.
A set of instances of the ID generated by each population member is analyzed to produce a separate xe2x80x9crepresentative bit patternxe2x80x9d for the ID indicating the most commonly occurring state of each bit of the member""s ID. The set of ID instances generated by each population member are also processed to determine a xe2x80x9cdrift profilexe2x80x9d for that member""s ID, the drift profile indicating for each bit position of the ID whether the bit in that position drifts and the probability that the bit position will contain a bit of a particular state. Thereafter, to verify that a particular object is a member of the population of objects, an instance of the ID of the particular object is first compared to the representative bit patterns of the IDs of the members of the population. If a sufficient number of the bits of that instance of the ID of the particular object are not of the same state as similar bits of the representative bit pattern of the ID of any population member, then the ID of the particular object is considered not to match the ID of any population member, and the particular object is therefore considered to be other than a member of the population.
Otherwise, if a sufficient number of the bits of the instance of the ID of the particular object are of the same state as similar bits of the representative bit pattern of the ID of one specific member of the population, then the ID of the object is considered to xe2x80x9cmatchxe2x80x9d the ID of that specific member. In such case, several instances of the ID of the particular object are obtained, and a drift profile for the ID of the particular object is calculated from those several ID instances. The drift profile of the ID of the particular object is then compared to the drift profile of the particular member""s matching ID to verify whether the particular object is that specific member of the population.
This ID verification system is more difficult to defeat than prior art systems that rely only on determining whether all, or a sufficient number, of the corresponding bits of two IDs are of matching states because it is more difficult for one to discover the drift profile of an ID that is subject to bit drift than to discover a single valid ID. It is also more difficult to produce a sequence of IDs having a particular drift profile than to produce a single ID having a particular set of fixed bit states. A would-be object counterfeiter might obtain a snapshot of one instance of an ID produced by a member of the population and attempt to adapt a counterfeit object to produce a static IC mimicking that particular ID instance, but the counterfeit object""s ID would be static and would fail to present the correct drift profile and will therefore be discernable as a counterfeit. Since the drift profiles of the IDs produced by members of the population are random and unpredictable, a counterfeiter not having access to members of the population or to a drift profile database would find it difficult to produce counterfeit objects presenting legitimate drift profiles.
The claims appended to this specification particularly point out and distinctly claim the subject matter of the invention. However those skilled in the art will best understand both the organization and method of operation of what the applicant(s) consider to be the best mode(s) of practicing the invention, together with further advantages and objects of the invention, by reading the remaining portions of the specification in view of the accompanying drawing(s) wherein like reference characters refer to like elements.